package com.jxl_dyw.hashMap;

import java.util.*;

public class MyHashMap<K, V> {
    // 初始容量为16
    private static final int INITIAL_CAPACITY = 16;
    // 负载因子为0.75
    private static final float LOAD_FACTOR = 0.75f;

    // 哈希表数组
    private Entry<K, V>[] table;
    // 哈希表元素数量
    private int size;
    // 扩容阈值
    private int threshold;

    // 构造函数，初始化哈希表
    public MyHashMap() {
        table = new Entry[INITIAL_CAPACITY];
        size = 0;
        threshold = (int) (INITIAL_CAPACITY * LOAD_FACTOR);
    }

    // 内部类，表示哈希表中的一个条目
    private static class Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 计算键的哈希值
    private int hash(Object key) {
        return (key == null) ? 0 : Math.abs(key.hashCode() % table.length);
    }

    // 插入键值对到哈希表中
    public void put(K key, V value) {
        int index = hash(key);
        Entry<K, V> newEntry = new Entry<>(key, value, null);

        // 如果桶为空，直接放入新条目
        if (table[index] == null) {
            table[index] = newEntry;
        } else {
            // 否则，遍历链表查找是否存在相同键，如果存在则更新值
            Entry<K, V> current = table[index];
            while (current.next != null) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            if (current.key.equals(key)) {
                current.value = value;
            } else {
                current.next = newEntry;
            }
        }

        size++;
        // 如果超过扩容阈值，进行扩容
        if (size >= threshold) {
            resize();
        }
    }

    // 根据键获取值
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> entry = table[index];

        // 遍历链表查找键，找到则返回值
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }

        return null;
    }

    // 根据键移除条目
    public V remove(K key) {
        int index = hash(key);
        Entry<K, V> previous = null;
        Entry<K, V> current = table[index];

        // 遍历链表查找键，找到则移除条目
        while (current != null) {
            if (current.key.equals(key)) {
                if (previous == null) {
                    table[index] = current.next;
                } else {
                    previous.next = current.next;
                }
                size--;
                return current.value;
            }
            previous = current;
            current = current.next;
        }

        return null;
    }

    // 扩容哈希表
    private void resize() {
        Entry<K, V>[] oldTable = table;
        table = new Entry[oldTable.length * 2];
        size = 0;
        threshold = (int) (table.length * LOAD_FACTOR);

        // 重新插入旧表中的所有条目到新表中
        for (Entry<K, V> entry : oldTable) {
            while (entry != null) {
                put(entry.key, entry.value);
                entry = entry.next;
            }
        }
    }

    // 获取哈希表中条目的数量
    public int size() {
        return size;
    }

    // 获取哈希表中所有的值
    public List<V> values() {
        List<V> values = new ArrayList<>();
        for (Entry<K, V> entry : table) {
            while (entry != null) {
                values.add(entry.value);
                entry = entry.next;
            }
        }
        return values;
    }

    // 获取哈希表中所有的键
    public List<K> keys() {
        List<K> keys = new ArrayList<>();
        for (Entry<K, V> entry : table) {
            while (entry != null) {
                keys.add(entry.key);
                entry = entry.next;
            }
        }
        return keys;
    }

    // 按照员工姓名的姓氏进行升序排序，姓氏相同则按后续字符排序
    public String[] sortByNameAsc(MyHashMap<String, V> map) {
        List<String> keys = map.keys();
        String[] sortedKeys = keys.toArray(new String[0]);

        // 使用 Collator 确保中文字符按照拼音排序
        Comparator<String> nameComparator = new Comparator<String>() {
            private final java.text.Collator collator = java.text.Collator.getInstance(Locale.CHINA);

            @Override
            public int compare(String o1, String o2) {
                // 分割姓名为姓和名
                String surname1 = o1.split("")[0];
                String surname2 = o2.split("")[0];

                // 首先按姓氏排序
                int surnameComparison = collator.compare(surname1, surname2);
                if (surnameComparison != 0) {
                    return surnameComparison;
                }

                // 如果姓氏相同，则按后续字符排序
                return collator.compare(o1, o2);
            }
        };

        // 对键数组进行排序
        Arrays.sort(sortedKeys, nameComparator);
        return sortedKeys;
    }

    // 按照员工姓名的姓氏进行降序排序，姓氏相同则按后续字符排序
    public String[] sortByNameDesc(MyHashMap<String, V> map) {
        List<String> keys = map.keys();
        String[] sortedKeys = keys.toArray(new String[0]);

        // 使用 Collator 确保中文字符按照拼音排序
        Comparator<String> nameComparator = new Comparator<String>() {
            private final java.text.Collator collator = java.text.Collator.getInstance(Locale.CHINA);

            @Override
            public int compare(String o1, String o2) {
                // 分割姓名为姓和名
                String surname1 = o1.split("")[0];
                String surname2 = o2.split("")[0];

                // 首先按姓氏排序
                int surnameComparison = collator.compare(surname1, surname2);
                if (surnameComparison != 0) {
                    return -surnameComparison; // 降序
                }

                // 如果姓氏相同，则按后续字符排序
                return -collator.compare(o1, o2); // 降序
            }
        };

        // 对键数组进行排序
        Arrays.sort(sortedKeys, nameComparator);
        return sortedKeys;
    }
}